package dp;

import java.util.Stack;

public class D230823 {
    // 最长的括号子串
    // 一个仅包含'(' ')' 的字符串，
    // 计算格式正确的最长子串

    // 1. 栈
    // 时间：O(N)
    // 空间：O(N)
    public int longestValidParentheses (String s) {
        int res = 0;
        // 记录上一次连续括号的结束的位置
        int start = -1;
        // Integer 存储下标
        Stack<Integer> st = new Stack<Integer>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 左括号入栈
                st.push(i);
            } else {
                // 右括号
                if (st.isEmpty()) {
                    // 栈为空的情况
                    // 不合法，设置结束位置
                    start = i;
                } else {
                    // 栈不为空，弹出左括号
                    st.pop();
                    if (!st.empty()) {
                        // 栈中还有元素（左括号）
                        // 当前下标，减栈顶左括号的下标，就是当前的有效的长度
                        res = Math.max(res, i - st.peek());
                    } else {
                        // 栈中已经没有元素的情况
                        // 那当前长度就是 当前下标 - 上次记录的位置
                        res = Math.max(res, i - start);
                    }
                }
            }
        }
        return res;
    }


    // 2. 动态规划
    // 时间：O(N)
    // 空间：O(N)
    public int longestValidParentheses2 (String s) {
        int res = 0;
        int n = s.length();
        // dp[i] 表示 s 的前 i 个字符，最长合法括号的长度
        int[] dp = new int[n];
        // 左括号作为结尾是不合法的，所以左括号都是 dp[i] = 0
        for (int i = 1; i < n; i++) {
            // 不用处理左括号，默认值就是 0、

            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    // 上一个是左括号
                    // 匹配一对括号，进行 + 2
                    // 需要判断下标
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0
                        && s.charAt(i - dp[i - 1] - 1) == '(') {
                    // 上一个是右括号
                    // 通过上一个右括号 dp[i - 1] 的长度
                    // 定位到，与当前右括号 匹配的 左括号
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0)
                            + dp[i - 1] + 2;
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
